home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / globber.exe / MATCH.C < prev    next >
C/C++ Source or Header  |  1991-03-12  |  17KB  |  522 lines
  1. /*
  2.  EPSHeader
  3.  
  4.    File: match.c
  5.    Author: J. Kercheval
  6.    Created: Sat, 01/05/1991  22:21:49
  7. */
  8. /*
  9.  EPSRevision History
  10.  
  11.    J. Kercheval  Wed, 02/20/1991  22:29:01  Released to Public Domain
  12.    J. Kercheval  Fri, 02/22/1991  15:29:01  fix '\' bugs (two :( of them)
  13.    J. Kercheval  Sun, 03/10/1991  19:31:29  add error return to matche()
  14.    J. Kercheval  Sun, 03/10/1991  20:11:11  add is_valid_pattern code
  15.    J. Kercheval  Sun, 03/10/1991  20:37:11  beef up main()
  16.    J. Kercheval  Tue, 03/12/1991  22:25:10  Released as V1.1 to Public Domain
  17. */
  18.  
  19. /*
  20.    Wildcard Pattern Matching
  21. */
  22.  
  23.  
  24. #include "match.h"
  25.  
  26. int matche_after_star (register char *pattern, register char *text);
  27. int fast_match_after_star (register char *pattern, register char *text);
  28.  
  29. /*----------------------------------------------------------------------------
  30. *
  31. * Return TRUE if PATTERN has any special wildcard characters
  32. *
  33. ----------------------------------------------------------------------------*/
  34.  
  35. BOOLEAN is_pattern (char *p)
  36. {
  37.     while ( *p ) {
  38.         switch ( *p++ ) {
  39.             case '?':
  40.             case '*':
  41.             case '[':
  42.             case '\\':
  43.                 return TRUE;
  44.         }
  45.     }
  46.     return FALSE;
  47. }
  48.  
  49.  
  50. /*----------------------------------------------------------------------------
  51. *
  52. * Return TRUE if PATTERN has is a well formed regular expression according
  53. * to the above syntax
  54. *
  55. * error_type is a return code based on the type of pattern error.  Zero is
  56. * returned in error_type if the pattern is a valid one.  error_type return
  57. * values are as follows:
  58. *
  59. *   PATTERN_VALID - pattern is well formed
  60. *   PATTERN_ESC   - pattern has invalid escape ('\' at end of pattern)
  61. *   PATTERN_RANGE - [..] construct has a no end range in a '-' pair (ie [a-])
  62. *   PATTERN_CLOSE - [..] construct has no end bracket (ie [abc-g )
  63. *   PATTERN_EMPTY - [..] construct is empty (ie [])
  64. *
  65. ----------------------------------------------------------------------------*/
  66.  
  67. BOOLEAN is_valid_pattern (char *p, int *error_type)
  68. {
  69.     
  70.     /* init error_type */
  71.     *error_type = PATTERN_VALID;
  72.     
  73.     /* loop through pattern to EOS */
  74.     while( *p ) {
  75.  
  76.         /* determine pattern type */
  77.         switch( *p ) {
  78.  
  79.             /* check literal escape, it cannot be at end of pattern */
  80.             case '\\':
  81.                 if( !*++p ) {
  82.                     *error_type = PATTERN_ESC;
  83.                     return FALSE;
  84.                 }
  85.                 p++;
  86.                 break;
  87.  
  88.             /* the [..] construct must be well formed */
  89.             case '[':
  90.                 p++;
  91.  
  92.                 /* if the next character is ']' then bad pattern */
  93.                 if ( *p == ']' ) {
  94.                     *error_type = PATTERN_EMPTY;
  95.                     return FALSE;
  96.                 }
  97.                 
  98.                 /* if end of pattern here then bad pattern */
  99.                 if ( !*p ) {
  100.                     *error_type = PATTERN_CLOSE;
  101.                     return FALSE;
  102.                 }
  103.  
  104.                 /* loop to end of [..] construct */
  105.                 while( *p != ']' ) {
  106.  
  107.                     /* check for literal escape */
  108.                     if( *p == '\\' ) {
  109.                         p++;
  110.  
  111.                         /* if end of pattern here then bad pattern */
  112.                         if ( !*p++ ) {
  113.                             *error_type = PATTERN_ESC;
  114.                             return FALSE;
  115.                         }
  116.                     }
  117.                     else
  118.                         p++;
  119.  
  120.                     /* if end of pattern here then bad pattern */
  121.                     if ( !*p ) {
  122.                         *error_type = PATTERN_CLOSE;
  123.                         return FALSE;
  124.                     }
  125.  
  126.                     /* if this a range */
  127.                     if( *p == '-' ) {
  128.  
  129.                         /* we must have an end of range */
  130.                         if ( !*++p || *p == ']' ) {
  131.                             *error_type = PATTERN_RANGE;
  132.                             return FALSE;
  133.                         }
  134.                         else {
  135.  
  136.                             /* check for literal escape */
  137.                             if( *p == '\\' )
  138.                                 p++;
  139.  
  140.                             /* if end of pattern here then bad pattern */
  141.                             if ( !*p++ ) {
  142.                                 *error_type = PATTERN_ESC;
  143.                                 return FALSE;
  144.                             }
  145.                         }
  146.                     }
  147.                 }
  148.                 break;
  149.  
  150.             /* all other characters are valid pattern elements */
  151.             case '*':
  152.             case '?':
  153.             default:
  154.                 p++;                              /* "normal" character */
  155.                 break;
  156.          }
  157.      }
  158.  
  159.      return TRUE;
  160. }
  161.  
  162.  
  163. /*----------------------------------------------------------------------------
  164. *
  165. *  Match the pattern PATTERN against the string TEXT;
  166. *
  167. *  returns MATCH_VALID if pattern matches, or an errorcode as follows
  168. *  otherwise:
  169. *
  170. *            MATCH_PATTERN  - bad pattern
  171. *            MATCH_LITERAL  - match failure on literal mismatch
  172. *            MATCH_RANGE    - match failure on [..] construct
  173. *            MATCH_ABORT    - premature end of text string
  174. *            MATCH_END      - premature end of pattern string
  175. *            MATCH_VALID    - valid match
  176. *
  177. *
  178. *  A match means the entire string TEXT is used up in matching.
  179. *
  180. *  In the pattern string:
  181. *       `*' matches any sequence of characters (zero or more)
  182. *       `?' matches any character
  183. *       [SET] matches any character in the specified set,
  184. *       [!SET] or [^SET] matches any character not in the specified set.
  185. *
  186. *  A set is composed of characters or ranges; a range looks like
  187. *  character hyphen character (as in 0-9 or A-Z).  [0-9a-zA-Z_] is the
  188. *  minimal set of characters allowed in the [..] pattern construct.
  189. *  Other characters are allowed (ie. 8 bit characters) if your system
  190. *  will support them.
  191. *
  192. *  To suppress the special syntactic significance of any of `[]*?!^-\',
  193. *  and match the character exactly, precede it with a `\'.
  194. *
  195. ----------------------------------------------------------------------------*/
  196.  
  197. int matche ( register char *p, register char *t )
  198. {
  199.     register char range_start, range_end;  /* start and end in range */
  200.  
  201.     BOOLEAN invert;             /* is this [..] or [!..] */
  202.     BOOLEAN member_match;       /* have I matched the [..] construct? */
  203.     BOOLEAN loop;               /* should I terminate? */
  204.  
  205.     for ( ; *p; p++, t++ ) {
  206.  
  207.         /* if this is the end of the text then this is the end of the match */
  208.         if (!*t) {
  209.             return ( *p == '*' && *++p == '\0' ) ? MATCH_VALID : MATCH_ABORT;
  210.         }
  211.  
  212.         /* determine and react to pattern type */
  213.         switch ( *p ) {
  214.  
  215.             /* single any character match */
  216.             case '?':
  217.                 break;
  218.  
  219.             /* multiple any character match */
  220.             case '*':
  221.                 return matche_after_star (p, t);
  222.  
  223.             /* [..] construct, single member/exclusion character match */
  224.             case '[': {
  225.  
  226.                 /* move to beginning of range */
  227.                 p++;
  228.  
  229.                 /* check if this is a member match or exclusion match */
  230.                 invert = FALSE;
  231.                 if ( *p == '!' || *p == '^') {
  232.                     invert = TRUE;
  233.                     p++;
  234.                 }
  235.  
  236.                 /* if closing bracket here or at range start then we have a
  237.                    malformed pattern */
  238.                 if ( *p == ']' ) {
  239.                     return MATCH_PATTERN;
  240.                 }
  241.  
  242.                 member_match = FALSE;
  243.                 loop = TRUE;
  244.  
  245.                 while ( loop ) {
  246.  
  247.                     /* if end of construct then loop is done */
  248.                     if (*p == ']') {
  249.                         loop = FALSE;
  250.                         continue;
  251.                     }
  252.  
  253.